/**
 * @file test.cpp
 * @author 张奕欣 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-11-23
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
#include "sorting.h"
#include <vector>
#include <string>
#include <cstdlib> 
#include <ctime>
#include <windows.h>
#include <math.h>
using namespace std;

/**
 * @brief 生成数组arr，有序程度为k，长度为n
 * 
 * @param arr 
 * @param n 
 * @param k 
 */
template <typename Comparable>
void shuzu(vector<Comparable> &arr, int n, float s)
{
    vector<Comparable>().swap(arr);
    if (s<0 | s>1)
    {
        cout << "Error S !";
        return;
    }
    if (s<=0.5)
    {
        int a = (int)n*(n-1)*s/2;
        double delta = n*n-4*a;
        int x = (int) (n+2+sqrt(delta))/2;
        for (int i =x;i<n+1;i++)
        {
            arr.push_back(i);
        }
        for (int i = 1; i < x ; i++) 
        {
            arr.push_back(i);
        }
    }
    else
    {
        s = 1-s;
        int a = (int)n*(n-1)*s/2;
        double delta = n*n-4*a;
        int x = (int) (n+2+sqrt(delta))/2;
        for (int i =x-1;i>0;i--)
        {
            arr.push_back(i);
        }
        for (int i = n; i > x-1 ; i--) 
        {
            arr.push_back(i);
        }
    }
}

/**
 * @brief 测试快速排序的效率
 * 
 * @tparam Comparable 
 * @param arr 
 * @param m 
 * @return float 
 */
template <typename Comparable>
float timeq(vector<Comparable> &arr,int m)
{
    vector<float> timeq1;
    for (int j = 0; j<m;j++)
    {
        double run_time;
	    _LARGE_INTEGER time_start;	//开始时间
	    _LARGE_INTEGER time_over;	//结束时间
	    double dqFreq;		//计时器频率
	    LARGE_INTEGER f;	//计时器频率
	    QueryPerformanceFrequency(&f);
	    dqFreq=(double)f.QuadPart;
	    QueryPerformanceCounter(&time_start);	//计时开始
        quicksort(arr);
        QueryPerformanceCounter(&time_over);	//计时结束
	    run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	    //乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
        timeq1.push_back(run_time);
    }

    float sumq = 0;
    for (int j = 0; j<m;j++)
    {
        sumq = sumq + timeq1[j];
    }
    return sumq/m;
}

/**
 * @brief 测试堆排序的效率
 * 
 * @tparam Comparable 
 * @param arr 
 * @param m 
 * @return float 
 */
template <typename Comparable>
float timeh(vector<Comparable> &arr,int m)
{
    vector<float> timeh1;
    for (int j = 0; j<m;j++)
    {
        double run_time;
	    _LARGE_INTEGER time_start;	//开始时间
	    _LARGE_INTEGER time_over;	//结束时间
	    double dqFreq;		//计时器频率
	    LARGE_INTEGER f;	//计时器频率
	    QueryPerformanceFrequency(&f);
	    dqFreq=(double)f.QuadPart;
	    QueryPerformanceCounter(&time_start);	//计时开始
        heapsort(arr);
        QueryPerformanceCounter(&time_over);	//计时结束
	    run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	    //乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
        timeh1.push_back(run_time);
    }

    float sumh = 0;
    for (int j = 0; j<m;j++)
    {
        sumh = sumh + timeh1[j];
    }
    return sumh/m;
}

/**
 * @brief 测试插入排序的效率
 * 
 * @tparam Comparable 
 * @param arr 
 * @param m 
 * @return float 
 */
template <typename Comparable>
float times(vector<Comparable> &arr,int m)
{
    vector<float> times1;
    for (int j = 0; j<m;j++)
    {
        double run_time;
	    _LARGE_INTEGER time_start;	//开始时间
	    _LARGE_INTEGER time_over;	//结束时间
	    double dqFreq;		//计时器频率
	    LARGE_INTEGER f;	//计时器频率
	    QueryPerformanceFrequency(&f);
	    dqFreq=(double)f.QuadPart;
	    QueryPerformanceCounter(&time_start);	//计时开始
        insertionSort(arr);
        QueryPerformanceCounter(&time_over);	//计时结束
	    run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	    //乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
        times1.push_back(run_time);
    }

    float sums = 0;
    for (int j = 0; j<m;j++)
    {
        sums = sums + times1[j];
    }
    return sums/m;
}

int main()
{
    /**
     * @brief k=1%
     * 
    */
    int n = 20000;  //数组长度为20000
    int m = 20;  //重复20次
    vector<int> l1;
    vector<double> TimeHeap;
    vector<double> TimeQuick;
    
    float s = 0.01;
    shuzu(l1,n,s);
    TimeHeap.push_back(timeh(l1,m));
    TimeQuick.push_back(timeq(l1,m));

    s =0.1;
    shuzu(l1,n,s);
    TimeHeap.push_back(timeh(l1,m));
    TimeQuick.push_back(timeq(l1,m));

    s =0.9;
    shuzu(l1,n,s);
    TimeHeap.push_back(timeh(l1,m));
    TimeQuick.push_back(timeq(l1,m));

    s =0.99;
    shuzu(l1,n,s);
    TimeHeap.push_back(timeh(l1,m));
    TimeQuick.push_back(timeq(l1,m));

    cout << "heapsort:" <<endl;
	for (int i=0;i<TimeHeap.size();i++)
    {
        cout<<TimeHeap.at(i)<< "us" <<endl;
    }

    cout << "quicksort:" <<endl;
	for (int i=0;i<TimeQuick.size();i++)
    {
        cout<<TimeQuick.at(i)<< "us" <<endl;
    }
    
    //=====================optimize==========================================
    /**
     * @brief 当数据基本有序时
     * 
     */
    vector<double> Timeq;
    vector<double> Timeoq;
    
    s = 0.01;
    vector<int> a ;
    shuzu(a,n,s);
    Timeoq.push_back(times(a,m));
    Timeq.push_back(timeq(a,m));

    s =0.005;
    shuzu(a,n,s);
    Timeoq.push_back(times(a,m));
    Timeq.push_back(timeq(a,m));

    s =0.001;
    shuzu(a,n,s);
    Timeoq.push_back(times(a,m));
    Timeq.push_back(timeq(a,m));

    s =0.0001;
    shuzu(a,n,s);
    Timeoq.push_back(times(a,m));
    Timeq.push_back(timeq(a,m));
    
    cout << "optimize quicksort when ordered:" <<endl;
	for (int i=0;i<Timeoq.size();i++)
    {
        cout<<Timeoq.at(i)<< "us" <<endl;
    }

    cout << "quicksort:" <<endl;
	for (int i=0;i<Timeq.size();i++)
    {
        cout<<Timeq.at(i)<< "us" <<endl;
    }

}